package com.nanbei.redblack;

/**
 * 红黑树的特点：
 * 1. 所有节点都有两种颜色：红、黑
 * 2. 所有 null 视为黑色
 * 3. 红色节点不能相邻
 * 4. 根节点是黑色
 * 5. 从根到任意一个叶子节点，路径中的黑色节点数一样
 *
 * @ClassDescription: 红黑树
 * @JdkVersion: 17
 * @Author: BaoShan.Li
 * @Date: 2024/6/5 21:22
 */
public class RedBlackTree {
    RedBlackNode root;

    public RedBlackTree() {

    }
    public RedBlackTree(RedBlackNode root) {
        this.root = root;
    }

    /**
     * 判断节点是否是红色
     * @param node 需要判断的节点
     * @return 是否是红色
     */
    public boolean isRed(RedBlackNode node){
        return node != null && node.color == Color.RED;
    }

    /**
     * 判断节点是否是红色
     * @param node 需要判断的节点
     * @return 是否是黑色
     */
    public boolean isBlack(RedBlackNode node){
        // 红黑树的null节点默认为黑色
        return node ==null || node.color == Color.BLACK;
    }

    /**
     *          。。。。。。
     *              8
     *          /       \
     *         5         10
     *       /   \     /   \
     *      3    6    9     11
     *    /  \    \
     *   2   4     7
     *  /
     * 1
     * 红黑树右旋
     * @param nodeParent 树节点 上树中的 8 节点
     */
    private void rightRotate(RedBlackNode nodeParent){
        // 获取nodeParent父节点
        RedBlackNode grand = nodeParent.parent;
        RedBlackNode node = nodeParent.left;
        RedBlackNode child = node.right;
        if (child != null){
            // 将 6 节点的父节点指向 8
            child.parent = nodeParent;
        }
        node.right = nodeParent;
        // 将 5 节点的父节点 指向 8 节点的父节点（如果8不为根节点时）
        node.parent = grand;
        nodeParent.left = child;
        // 将8 节点的父节点指向 5 节点
        nodeParent.parent = node;
        if (grand == null){
            // 如果8 节点的父节点为空，则8在旋转前为根节点，旋转后的根节点为5.
            root = node;
        }else if (grand.left == nodeParent){
            // 如果旋转前8为父节点的左孩子，则经过旋转后 5也为左节点。
            grand.left = node;
        }else {
            grand.right = node;
        }

    }

    /**
     *          。。。。。。
     *              8
     *          /       \
     *         5         15
     *       /   \     /   \
     *      3    6    13    16
     *               /  \    \
     *              12  14   17
     *                         \
     *                         18
     * 红黑树左旋
     * @param nodeParent 树节点 上树中的 8 节点
     */
    private void leftRotate(RedBlackNode nodeParent){
        RedBlackNode grand = nodeParent.parent;
        RedBlackNode node = nodeParent.right;
        RedBlackNode child = node.left;
        if (child != null){
            child.parent = nodeParent;
        }
        node.left = nodeParent;
        node.parent = grand;
        nodeParent.right = child;
        nodeParent.parent = node;
        if (grand == null){
            root = node;
        }else if (grand.left == nodeParent){
            grand.left = node;
        }else {
            grand.right = node;
        }
    }


    /**
     * 新增或者更新
     * 正常新增，或者遇到红红不平衡的时候进行调整
     * @param key 键
     * @param val 值
     */
    public void put(int key,Object val){
        RedBlackNode node = root ;
        // 记录新增节点的父节点
        RedBlackNode parent = null;
        // 寻找要插入节点的位置
        while (node != null){
            parent = node;
            if (node.key < key){
                node = node.right;
            } else if (node.key > key) {
                node = node.left;
            }else {
                node.value = val;
                return;
            }
        }

        //  创建新的红黑树节点
        RedBlackNode inserRredBlackNode = new RedBlackNode(key, val);
        if (parent == null){
            // 则创建的节点为根节点
            root = inserRredBlackNode;
        }else if (key < parent.key){  // 创建的节点插入到父节点的左边
            parent.left = inserRredBlackNode;
            inserRredBlackNode.parent = parent;
        }else {
            parent.right = inserRredBlackNode;
            inserRredBlackNode.parent = parent;
        }
        // 插入的节点默认为红色，如果遇见红红，则需要进行调整
        fixRedRed(inserRredBlackNode);

    }

    /**
     * 调整红红节点的方法
     * 插入节点均视为红色:
     *
     * case 1：插入节点为根节点，将根节点变黑:
     *
     * case 2：插入节点的父亲若为黑色:，树的红黑性质不变，无需调整
     *
     *
     *
     * 插入节点的父亲为红色:，触发红红相邻
     *
     * case 3：叔叔为红色:
     *
     * - 父亲变为黑色:，为了保证黑色平衡，连带的叔叔也变为黑色:
     * - 祖父如果是黑色不变，会造成这颗子树黑色过多，因此祖父节点变为红色:
     * - 祖父如果变成红色，可能会接着触发红红相邻，因此对将祖父进行递归调整
     *
     * case 4：叔叔为黑色:
     *
     * 1. 父亲为左孩子，插入节点也是左孩子，此时即 LL 不平衡
     *    - 让父亲变黑:，为了保证这颗子树黑色不变，将祖父变成红:，但叔叔子树少了一个黑色
     *    - 祖父右旋，补齐一个黑色给叔叔，父亲旋转上去取代祖父，由于它是黑色，不会再次触发红红相邻
     * 2. 父亲为左孩子，插入节点是右孩子，此时即 LR 不平衡
     *    - 父亲左旋，变成 LL 情况，按 1. 来后续处理
     * 3. 父亲为右孩子，插入节点也是右孩子，此时即 RR 不平衡
     *    - 让父亲变黑:，为了保证这颗子树黑色不变，将祖父变成红:，但叔叔子树少了一个黑色
     *    - 祖父左旋，补齐一个黑色给叔叔，父亲旋转上去取代祖父，由于它是黑色，不会再次触发红红相邻
     * 4. 父亲为右孩子，插入节点是左孩子，此时即 RL 不平衡
     *    - 父亲右旋，变成 RR 情况，按 3. 来后续处理
     * 
     * @param node 插入的节点 ；
     */
    private void fixRedRed(RedBlackNode node){
        // node节点为根节点
        if (node == root){
            node.color = Color.BLACK;
            return;
        }
        // 如果插入的父节点为黑色，则无需调整
        if (isBlack(node.parent)){
            return;
        }
        // 当叔叔节点为红色时 : 将父节点和叔叔节点调为黑色，将爷爷节点调为红色，在递归调用爷爷节点
        RedBlackNode parent = node.parent;
        RedBlackNode uncle = node.uncle();
        RedBlackNode grand = parent.parent;
        if (isRed(uncle)){
            parent.color = Color.BLACK;
            uncle.color = Color.BLACK;
            grand.color = Color.RED;
            fixRedRed(grand);
            return;
        }
        // 当叔叔节点为黑色时(如果叔叔节点为null,null也默认为黑色节点)
        if (parent.isLeftChild() && node.isLeftChild()){ //   LL 不平衡
            //1. 父亲变黑
            parent.color = Color.BLACK;
            // 2. 祖父变红
            grand.color=Color.RED;
            // 3. 祖父右旋
            rightRotate(grand);
        } else if (parent.isLeftChild() && !node.isLeftChild()) { // LR 不平衡
            // 1. 父节 点左旋
            leftRotate(parent);
            // 2. 新插入的节点变为父节点， 然后颜色变为黑色
            node.color = Color.BLACK;
            // 3. 爷爷节点颜色变为红色
            grand.color= Color.RED;
            // 4. 最后进行右旋
            rightRotate(grand);
        } else if (!parent.isLeftChild() && !node.isLeftChild()) { // RR
            //1. 父亲变黑
            parent.color = Color.BLACK;
            // 2. 祖父变红
            grand.color=Color.RED;
            // 3. 祖父左旋
            leftRotate(grand);

        }else { // RL
            // 1. 父节 右旋
            rightRotate(parent);
            // 2. 新插入的节点变为父节点， 然后颜色变为黑色
            node.color = Color.BLACK;
            // 3. 爷爷节点颜色变为红色
            grand.color= Color.RED;
            // 4. 最后进行左旋
            leftRotate(grand);
        }

    }


    /**
     * 删除
     *
     * 1. 如果被删除的节点既有左孩子又有右孩子：
     *    - 将要删除的节点和后继节点的K、V相互交换，交换后递归调用删除后继节点即可；
     *
     * 2. 如果被删除的节点只有一个孩子：
     *   - 则被删除的节点一定为黑色，且孩子为红色。将孩子节点替换从要删除的节点，颜色变为黑色。
     *
     *
     * 3. 如果被删除的节点没有孩子：
     *   - 如果被删除的颜色为红色，直接删除
     *   - 如果被删除节点为根节点，root = null；
     *   - 如果被删除节点的黑色，触发 黑黑  需要进行平衡调整：
     *      case4: 被调整节点的兄弟节点为黑，两个侄子都是黑色(实际上为两个孩子都为null)
     *          - 如果父节点为红色 -->
     *               将父节点的颜色变为黑色，兄弟节点的颜色变为红色；
     *          - 如果父节点为黑色 --> 删除后少了一个黑色
     *               将兄弟节点的颜色变为红色，然后递归调用父节点；
     *      case5: 被调整节点的兄弟节点为黑，两个侄子有一个为红色
     *          - 如果兄弟是左孩子，左侄子是红色，LL不平衡；
     *              左侄子颜色变黑，
     *              兄弟节点的颜色变成父节点的颜色
     *              父节点进行右旋
     *              父节点颜色变为黑色
     *          - 如果兄弟是左孩子，右侄子是红色，LR不平衡；
     *               将右侄子的颜色变为父节点的颜色 （防止旋转之后节点发生变化）
     *               将兄弟节点进行左旋
     *               将父节点进行右旋
     *               父节点颜色变为黑色
     *          - 如果兄弟是右孩子，右侄子是红色，RR不平衡；
     *              右侄子颜色变黑，
     *              兄弟节点的颜色变成父节点的颜色
     *              父节点进行左旋
     *              父节点颜色变为黑色
     *          - 如果兄弟是右孩子，左侄子是红色，RL不平衡；
     *               将左侄子的颜色变为父节点的颜色 （防止旋转之后节点发生变化）
     *               将兄弟节点进行右旋
     *               将父节点进行左旋
     *               父节点颜色变为黑色
     *        case3: 需要调整节点的兄弟节点为红色
     *            将要调整的兄弟节点进行左旋或者右旋，转换成 case4 或者case5的情况
     *             被删除节点为左孩子 -> 父节点进行左旋
     *             被删除节点为右孩子 -> 父节点进行右旋
     * @param key 键
     */
    public void remove(int key){
        RedBlackNode delNode =  findNode(key);
        if (delNode ==null){
            return;
        }
        doRemove(delNode);
    }

    private void doRemove(RedBlackNode delNode) {
        //找到要删除节点的后继节点
        RedBlackNode replaceNode = findReplace(delNode);
        RedBlackNode delParent = delNode.parent;

        // 没有孩子
        if (replaceNode == null) {
            // case1:待删除节点为根节点
            if (delNode == root) {
                root = null;
            } else {
                if (isBlack(delNode)) {
                    // 如果被删除的叶子节点为黑色需要做复杂处理，
                    fixDoubleBlack(delNode);
                } else {
                    // case2:
                    // 如果被删除的叶子节点为红色则直接删除.无需调整
                }

                // 将被删除节点的左右孩子及父节点置为NULL  便于垃圾回收；
                if (delNode.isLeftChild()) {
                    delParent.left = null;
                } else {
                    delParent.right = null;
                }
                delNode.parent = null;
            }
            return;
        }
        // 删除节点只有一个孩子
        if (delNode.left == null || delNode.right == null) {
            if (delNode == root) {
                // case1:待删除节点为根节点
                root.key = replaceNode.key;
                root.value = replaceNode.value;
                root.right = null;
                root.left = null;
            }else {
                // 判断被删除节点是父亲的左孩子还是右孩子
                // 然后将替换节点赋值给删除节点的父节点
                if (delNode.isLeftChild()){
                    delParent.left = replaceNode;
                }else {
                    delParent.right = replaceNode;
                }
                // 将替换节点的父节点指向被删除节点的父节点
                replaceNode.parent = delParent;
                // 将被删除节点的左右孩子及父节点置为NULL  便于垃圾回收；
                delNode.left = delNode.right = delNode.parent = null;

                if (isBlack(delNode) && isBlack(replaceNode)){
                    // 删除节点和替换节点都是黑色，需要复杂处理；
                    // 实际不会有这种情况 因为只有一个孩子时 被删除节点是黑色 那么剩余节点只能是红色不会触发双黑
                    // 如果剩下的一个节点为黑色，则这可红黑树会不平衡
                    // fixDoubleBlack(replaceNode);
                }else {
                    // case2:
                    // 删除节点为黑色，只有一个孩子且孩子为红色，
                    // 则将孩子节点的颜色改为黑色
                    replaceNode.color = Color.BLACK;
                }

            }
            return;
        }

        // case0 : 删除的节点既有左孩子又有右孩子
        // 交换要删除节点 和 后继节点的key和value ，交换后直接删除后继节点即可；
        int k = delNode.key;
        delNode.key = replaceNode.key;
        replaceNode.key = k;

        Object v = replaceNode.value;
        replaceNode.value = delNode.value;
        delNode.value = v;
        doRemove(replaceNode);
    }

    /**
     *  双黑节点调整
     * @param regulateNode 需要调整的节点
     */
    private void fixDoubleBlack(RedBlackNode regulateNode){
        if (regulateNode == root){
            return;
        }

        RedBlackNode parent = regulateNode.parent;
        RedBlackNode sibling = regulateNode.sibling();
        if (isRed(sibling)){
            // case3: 需要调整节点的兄弟节点为红色
            // 将要调整的兄弟节点进行左旋或者右旋，转换成 case4 或者case5的情况
            if (regulateNode.isLeftChild()){
                leftRotate(parent);
            }else {
                rightRotate(parent);
            }
            parent.color = Color.RED;
            sibling.color = Color.BLACK;
            fixDoubleBlack(regulateNode);
            return;
        }
        if (sibling != null){
            if (isBlack(sibling.left) && isBlack(sibling.right)){
                //case4: 被调整节点的兄弟节点为黑，两个侄子都是黑色
                // 1. 将兄地变红；
                // 2. 如果父节点为红色，则将颜色调整为黑色
                //    如果父节点为黑色，则说明路径中少了一个黑色，则递归调用父节点
                sibling.color = Color.RED;
                if (isRed(parent)){
                    parent.color=Color.BLACK;
                }else {
                    fixDoubleBlack(parent);
                }
            }else {
                //case5: 被调整节点的兄弟节点为黑，侄子右红色
                // 如果兄弟是左孩子，左侄子是红色，LL不平衡；
                // 如果兄弟是左孩子，右侄子是红色，LR不平衡；
                // 如果兄弟是右孩子，右侄子是红色，RR不平衡；
                // 如果兄弟是右孩子，左侄子是红色，RL不平衡；
                if (sibling.isLeftChild() && isRed(sibling.left)){ //LL
                    rightRotate(parent);
                    sibling.left.color = Color.BLACK;
                    sibling.color = parent.color;

                } else if (sibling.isLeftChild() && isRed(sibling.right)) { //LR
                    // 将变色代码放在左旋之前
                    sibling.right.color = parent.color;
                    leftRotate(sibling);
                    rightRotate(parent);
                }else if (!sibling.isLeftChild() && isRed(sibling.right)){ //RR
                    leftRotate(parent);
                    sibling.right.color = Color.BLACK;
                    sibling.color = parent.color;
                }else {// RL
                    // 将变色代码放在左旋之前
                    sibling.left.color = parent.color;
                    rightRotate(sibling);
                    leftRotate(parent);
                }
                parent.color =  Color.BLACK;
            }
        }else {
            // 实际不会触发， 如果被删除节点为黑色，则其兄弟节点不会为空。不然红黑树不平横，不能满足特点5
            // 触发双黑， 兄弟节点不会为null
            // fixDoubleBlack(parent);
        }



    }

    /**
     * chaz需要删除的节点
     * @param key key
     * @return 返回需要删除的节点
     */
    private RedBlackNode findNode(int key) {
        RedBlackNode node = root;
        while (node != null) {
            if (node.key > key) {
                node = node.left;
            } else if (node.key < key) {
                node = node.right;
            } else {
                return node;
            }
        }
        return null;
    }


    /**
     * 查找节点删除后的剩余节点，（如果左右孩子都有则返回后继节点）
     * @param delNode 需要删除的节点
     * @return 删除节点的替换节点
     */
    private RedBlackNode findReplace(RedBlackNode delNode) {
        if (delNode.right == null && delNode.left == null) {
            return null;
        } else if (delNode.right == null) {
            return delNode.left;
        } else if (delNode.left == null) {
            return delNode.right;
        } else {
            RedBlackNode successor = delNode.right;
            while (successor.left != null) {
                successor = successor.left;
            }
            return successor;
        }
    }


    public boolean contains(int key) {
        return findNode(key) != null;
    }




}
